class Solution:
    def __init__(self):
        self.cache = {}


    def _get_width(self, n):
        res = 1
        while n // res // 10 != 0:
            res *= 10
        return res

    def countDigitOne(self, n: int) -> int:
        if n == 0:
            return 0
        if n in self.cache:
            return self.cache[n]
        width = self._get_width(n)
        # 第一位
        first = n // width
        below_cnt = self.countDigitOne(width - 1)
        other = n % width
        if first == 1:
            res = below_cnt + 1 + other + self.countDigitOne(other)
        else:
            res = (below_cnt * (first - 2)) + self.countDigitOne(2* width - 1) + self.countDigitOne(other)
        self.cache[n] = res
        # print(n, self.cache)
        return res

if __name__ == "__main__":
    s = Solution()
    print(s.countDigitOne(23))
    # print(s.countDigitOne(9))
